// class Solution {
//     public int[] sortArray(int[] nums) {
//         if (nums.length == 1) {
//             return nums;
//         }
//         quick_sort(nums, 0, nums.length - 1);
//         return nums;
//     }

//     private  void quick_sort(int[] nums, int start, int end) {
//         // 递归的出口
//         if (start >= end) {
//             return;
//         }
//         // 利用三数取中法，拿到中间值
//         int index = medianOfThree(nums, start, end);
//         // 交换中间值与原基准，变为二叉树的形式
//         swap(nums, index, start);
//         // 新的基准值
//         int key = nums[start];
//         int left = start, right = end;

//         while (left != right) {
//             while (left < right && nums[right] >= key) {
//                 right--;
//             }

//             while (left < right && nums[left] <= key) {
//                 left++;
//             }
//             swap(nums, left, right);
//         }

//         swap(nums, start, right);

//         // 继续处理
//         quick_sort(nums, start, right - 1);
//         quick_sort(nums, right + 1, end);
//     }

//     private  int medianOfThree(int[] nums, int low, int high) {
//         int mid = (low + high) / 2;
//         int a = nums[low], b = nums[mid], c = nums[high];

//         if (a > b) {
//             if (a < c) {
//                 return low;
//             } else if (b > c) {
//                 return mid;
//             } else {
//                 return high;
//             }
//         } else {
//             if (a > c) {
//                 return low;
//             } else if (b < c) {
//                 return mid;
//             } else {
//                 return high;
//             }
//         }
//     }

//     private void swap(int[] nums, int i, int j) {
//         int temp = nums[i];
//         nums[i] = nums[j];
//         nums[j] = temp;
//     }
// }

// class Solution {
//     public int[] sortArray(int[] nums) {
//         quick_sort(nums, 0, nums.length - 1);
//         return nums;
//     }

//     private void quick_sort(int[] nums, int start, int end) {
//         // 递归的出口
//         if (start >= end) {
//             return;
//         }
//         // 利用三数取中法，拿到中间值
//         int index = medianOfThree(nums, start, end);
//         // 交换中间值与原基准值，变为二叉树的形式
//         swap(nums, index, start);
//         // 新的基准值
//         int key = nums[start];
//         int left = start-1, right = end+1;
//         for (int i = start; i != right;) {
//             int j = nums[i];
//             if (j < key) {
//                 swap(nums, ++left, i++);
//             } else if (j > key) {
//                 swap(nums, i, --right);
//             } else {
//                 i++;
//             }
//         }
//         // 递归 左子树、右子树
//         // 注意起始位置与结束位置
//         quick_sort(nums, start, left);
//         quick_sort(nums, right, end);
//     }

//     private int medianOfThree(int[] nums, int low, int high) {
//         int mid = (low + high) / 2;
//         int a = nums[low], b = nums[mid], c = nums[high];

//         if (a > b) {
//             if (a < c) {
//                 return low;
//             } else if (b > c) {
//                 return mid;
//             } else {
//                 return high;
//             }
//         } else {
//             if (a > c) {
//                 return low;
//             } else if (b < c) {
//                 return mid;
//             } else {
//                 return high;
//             }
//         }
//     }

//     private void swap(int[] nums, int i, int j) {
//         int temp = nums[i];
//         nums[i] = nums[j];
//         nums[j] = temp;
//     }
// }


import java.util.Random;

class Solution {
    public int[] sortArray(int[] nums) {
        quick_sort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quick_sort(int[] nums, int start, int end) {
        // 递归的出口
        if (start >= end) {
            return;
        }
        // 生成随机数，作为基准值
        int key = nums[new Random().nextInt(end-start+1)+start];
        int left = start-1, right = end+1;
        for (int i = start; i != right;) {
            int j = nums[i];
            if (j < key) {
                swap(nums, ++left, i++);
            } else if (j > key) {
                swap(nums, i, --right);
            } else {
                i++;
            }
        }
        // 递归 左子树、右子树
        // 注意起始位置与结束位置
        quick_sort(nums, start, left);
        quick_sort(nums, right, end);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}